package com.nulldev.util.data.Arrays.arrays;

import java.io.Serializable;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.RandomAccess;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
import java.util.function.Consumer;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

import com.nulldev.util.JVM.JVM;
import com.nulldev.util.VariableAPI.ArrayUtils;
import com.nulldev.util.VariableAPI.MathUtil;
import com.nulldev.util.concurrency.threadIt.v4.emapi.ExecutorManager;
import com.nulldev.util.data.Variables;
import com.nulldev.util.internal.backport.arrays.BackportArrays;

public class ConcurrentList<E> implements List<E>, RandomAccess, Serializable, Cloneable {

	/*
	 * Apparently single-linked lists are a thing, just don't try and query
	 * something at the back because O(n). TODO: Make a double linked variant of me.
	 */

	private static final long serialVersionUID = -9130113509109965074L;

	private final AtomicInteger size = new AtomicInteger();

	private class ListNode implements Cloneable {
		protected final AtomicReference<ListNode> next = new AtomicReference<ListNode>();
		protected final AtomicReference<E> value = new AtomicReference<E>();
		protected final AtomicInteger index = new AtomicInteger(-1);

		public ListNode() {
		}

		public ListNode(final E value) {
			this(value, ConcurrentList.this.size.getAndIncrement());
		}

		public ListNode(final E value, final int index) {
			this.value.set(value);
			this.index.set(index);
		}

		public boolean isSet() {
			return this.value.get() != null && this.index.get() > -1;
		}

		public synchronized void setAndKeepIndex(E e) {
			this.index.set(ConcurrentList.this.size.get());
			this.value.set(e);
		}

		public synchronized void setAndIncrementIndex(E e) {
			this.index.set(ConcurrentList.this.size.getAndIncrement());
			this.value.set(e);
		}

		@Override
		public String toString() {
			return "ListNode[hash=" + MathUtil.toHex(super.hashCode()) + ",index=" + this.index.get() + ",value=" + this.value.get() + ",hasNext="
					+ (this.next.get() != null) + "]";
		}

		public synchronized void reset() {
			this.value.set(null);
			this.index.set(-1);
		}

		public ListNode next() {
			return this.next.get();
		}

		public ListNode nextNonNull() {
			if (!this.hasNext())
				return null;
			ListNode next = this.next();
			if (this.next == null)
				return null;
			while (next != null && !next.isSet())
				next = next.next();
			return next;
		}

		public E value() {
			return this.value.get();
		}

		public synchronized void next(final ListNode listNode) {
			this.next.set(listNode);
		}

		public synchronized void lazyNext(final ListNode listNode) {
			this.next.lazySet(listNode);
		}

		public synchronized void value(final E element) {
			this.value.set(element);
		}

		public int index() {
			return this.index.get();
		}

		public boolean hasNext() {
			return this.next.get() != null;
		}

		@Override
		protected Object clone() throws CloneNotSupportedException {
			return new ListNode(this.value.get(), this.index.get());
		}

	}

	private final AtomicReference<ListNode> root = new AtomicReference<ListNode>();

	private ListNode getLastNode() {
		if (this.root.get() == null)
			return null;
		ListNode last;
		ListNode curr = this.root.get();
		while (true) {
			if (curr == null)
				return null;
			if (curr.next() == null) {
				last = curr;
				break;
			} else {
				curr = curr.next();
			}
		}
		return last;
	}

	private ListNode getNodeAt(final int index) {
		if (index < 0)
			throw new IllegalArgumentException("index < 0!");
		else if (this.root.get() == null)
			return null;
		ListNode node = null;
		ListNode curr = this.root.get();
		while (true) {
			if (curr == null)
				break;
			if (curr.index() == index) {
				node = curr;
				break;
			} else if (curr.next() == null) {
				break;
			} else {
				curr = curr.next();
			}
		}
		return node;
	}

	public ConcurrentList() {
		this.root.lazySet(new ListNode());
	}

	// FIXME: I should be pre-allocating instead of setting the size to N!
	public ConcurrentList(final int size) {
		this.root.lazySet(new ListNode());
		if (size > 0) {
			if (size > 1)
				for (int i = 0; i < size - 1; i++) {
					this.root.get().lazyNext(new ListNode());
				}
		}
	}

	public ConcurrentList(final Collection<? extends E> c) {
		this.root.lazySet(new ListNode());
		this.addAll(c);
	}

	@Override
	public int size() {
//		return this.actualSize.get();
		return this.size.get();
	}

	@Override
	public boolean isEmpty() {
//		return this.actualSize.get() <= 0;
		return this.size.get() <= 0;
	}

	@Override
	public boolean contains(Object o) {
		if (o == null)
			return false;
		ListNode curr = this.root.get();
		while (true) {
			if (o.equals(curr.value())) {
				return true;
			} else if (curr.next() == null) {
				break;
			} else {
				curr = curr.next();
			}
		}
		return false;
	}

	@Override
	public Iterator<E> iterator() {
		return this.iterator(true);
	}

	public Iterator<E> iterator(final boolean ENFORCE_NON_NULL_OBJECTS) {
		return new Iterator<E>() {

			final AtomicReference<ListNode> curr = new AtomicReference<ListNode>(ConcurrentList.this.root.get());

			@Override
			public boolean hasNext() {
				return this.curr.get() != null;
			}

			@Override
			public E next() {
				// FIXME: I sometimes still return a null pointer!
				if (this.curr.get() == null)
					throw new NoSuchElementException();
				final E v = this.curr.get().value();
				if (ENFORCE_NON_NULL_OBJECTS)
					this.curr.lazySet(this.curr.get().nextNonNull());
				else
					this.curr.lazySet(this.curr.get().next());
//				if ((this.curr.get() != null && !this.curr.get().isSet()) && ENFORCE_NON_NULL_OBJECTS)
//					this.curr.lazySet(this.curr.get().next());
				return v;
			}
		};
	}

	@Override
	public Object[] toArray() {
		if (this.isEmpty() || this.root.get() == null)
			return new Object[0];
		final Object[] o = new Object[this.size.get()];
		ListNode curr = this.root.get();
		while (true) {
			o[curr.index()] = curr.value();
			if (curr.next() == null) {
				break;
			} else {
				curr = curr.next();
			}
		}
		return o;
	}

	@SuppressWarnings("unchecked")
	@Override
	public <T> T[] toArray(T[] a) {
		if (this.size.get() == 0 || this.root.get() == null)
			return a;
		if (a.length == this.size()) {
			ListNode curr = this.root.get();
			while (true) {
				a[curr.index()] = (T) curr.value();
				if (curr.next() == null) {
					break;
				} else {
					curr = curr.next();
				}
			}
			return a;
		} else {
			ListNode curr = this.root.get();
			while (true && curr.index() < a.length) {
				a[curr.index()] = (T) curr.value();
				if (curr.next() == null) {
					break;
				} else {
					curr = curr.next();
				}
			}
			return a;
		}
	}

	@Override
	public boolean add(E e) {
		if (e == null) {
			return false;
		} else if (this.root.get() == null) {
			this.root.set(new ListNode(e));
		} else {
			final ListNode last = getLastNode();
			if (last.isSet()) {
				last.next(new ListNode(e));
			} else {
				last.setAndIncrementIndex(e);
			}
		}
		return true;
	}

	@Override
	public boolean remove(Object o) {
		if (o == null)
			return false;
		ListNode curr = this.root.get();
		while (true) {
			if (o.equals(curr.value())) {
				curr.reset();
				this.size.decrementAndGet();
				return true;
			} else if (curr.next() == null) {
				break;
			} else {
				curr = curr.next();
			}
		}
		return false;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		for (final Object o : c) {
			if (o == null)
				continue;
			if (!this.contains(o))
				return false;
		}
		return true;
	}

	@Override
	public boolean addAll(Collection<? extends E> c) {
		for (final E e : c) {
			if (e == null)
				continue;
			if (!this.add(e))
				return false;
		}
		return true;
	}

	@Override
	public boolean addAll(int index, Collection<? extends E> c) {
		// TODO
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		for (final Object e : c) {
			if (e == null)
				continue;
			if (!this.remove(e))
				return false;
		}
		return true;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		// TODO
		throw new UnsupportedOperationException();
	}

	@Override
	public void clear() {
		this.size.lazySet(0);
		this.root.lazySet(null);
	}

	@Override
	public E get(int index) {
		if (this.root.get() == null || index > this.size())
			return null;
		ListNode node = null;
		ListNode curr = this.root.get();
		while (true) {
			if (curr.index() == index) {
				node = curr;
				break;
			} else if (curr.next() == null) {
				break;
			} else {
				curr = curr.next();
			}
		}
		if (node == null)
			return null;
		else
			return node.value();
	}

	@Override
	public E set(int index, E element) {
		if (index < 0 || element == null)
			return null;
		final ListNode n = getNodeAt(index);
		if (n == null)
			return null;
		final E prev = n.value();
		n.value(element);
		return prev;
	}

	@Override
	public void add(int index, E element) {
		if (index < 0 || element == null)
			return;
		// TODO
		final ListNode n = getNodeAt(index);
		if (!n.isSet()) {
			n.setAndKeepIndex(element);
		} else if (n.hasNext()) {
			final ListNode newCurrent = new ListNode();
			newCurrent.value(element);
			newCurrent.index.set(index);
			throw new UnsupportedOperationException();
		} else {
			throw new UnsupportedOperationException();
		}
	}

	@Override
	public E remove(int index) {
		if (index < 0)
			return null;
		final ListNode n = getNodeAt(index);
		if (n == null)
			return null;
		final E prev = n.value();
		n.reset();
		this.size.decrementAndGet();
		return prev;
	}

	@Override
	public int indexOf(final Object o) {
		if (o == null)
			return -1;
		ListNode curr = this.root.get();
		while (true) {
			if (o.equals(curr.value())) {
				return curr.index();
			} else if (curr.next() == null) {
				break;
			} else {
				curr = curr.next();
			}
		}
		return -1;
	}

	@Override
	public int lastIndexOf(final Object o) {
		if (o == null)
			return -1;
		int index = -1;
		ListNode curr = this.root.get();
		while (true) {
			if (o.equals(curr.value())) {
				index = curr.index();
			} else if (curr.next() == null) {
				break;
			} else {
				curr = curr.next();
			}
		}
		return index;
	}

	@Override
	public ListIterator<E> listIterator() {
		return this.listIterator(0, true);
	}

	@Override
	public ListIterator<E> listIterator(final int index) {
		return this.listIterator(index, true);
	}

	public ListIterator<E> listIterator(final int index, final boolean ENFORCE_NON_NULL_OBJECTS) {
		return new ListIterator<E>() {
			final AtomicReference<ListNode> curr = new AtomicReference<ListNode>(getNodeAt(index));
			final AtomicBoolean hasReadInitialNode = new AtomicBoolean(false);

			@Override
			public boolean hasNext() {
				return this.curr.get() != null && this.curr.get().hasNext();
			}

			@Override
			public E next() {
				if (this.curr.get() == null)
					return null;
				else if (!this.hasReadInitialNode.get()) {
					this.hasReadInitialNode.lazySet(true);
					return this.curr.get().value();
				} else if (!this.curr.get().hasNext()) {
					final E out = this.curr.get().value();
					this.curr.lazySet(ENFORCE_NON_NULL_OBJECTS ? this.curr.get().nextNonNull() : this.curr.get().next());
					return out;
				} else {
					final ListNode lv = (ENFORCE_NON_NULL_OBJECTS ? this.curr.get().nextNonNull() : this.curr.get().next());
					final E out = lv.value();
					this.curr.lazySet(lv);
					return out;
				}
			}

			@Override
			public boolean hasPrevious() {
				return false;
			}

			@Override
			public E previous() {
				throw new UnsupportedOperationException();
			}

			@Override
			public int nextIndex() {
				if (this.curr.get() == null)
					return -1;
				else if (this.curr.get().hasNext())
					return this.curr.get().next().index();
				else
					return -1;
			}

			@Override
			public int previousIndex() {
				if (this.curr.get() == null)
					return -1;
				else if (this.curr.get().index() == 0)
					return -1;
				else
					return this.curr.get().index() - 1;
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();
			}

			@Override
			public void set(E e) {
				if (e == null)
					return;
				if (this.curr.get() == null)
					return;
				this.curr.get().setAndKeepIndex(e);
			}

			@Override
			public void add(E e) {
				throw new UnsupportedOperationException();
			}
		};
	}

	@Override
	public List<E> subList(int fromIndex, int toIndex) {
		final ConcurrentList<E> list = new ConcurrentList<E>(toIndex - fromIndex);
		for (int i = fromIndex; i < toIndex; i++) {
			list.add(this.get(i));
		}
		return list;
	}

	@Override
	public void sort(Comparator<? super E> c) {
		this.navSort(c);
	}

	@Override
	protected Object clone() throws CloneNotSupportedException {
		return super.clone();
	}

	@SuppressWarnings(
		{ "rawtypes", "unchecked" })
	public void navSort(final Comparator<? super E> c) {
		if (this.size.get() <= 1)
			return;
		final Object[] a = this.toArray();
		BackportArrays.sort(a, (Comparator) c);
		final ListNode rootNode = new ListNode();
		this.root.lazySet(rootNode);
		ListNode curr = rootNode;
		for (int i = 0; i < a.length; i++) {
			curr.value.lazySet((E) a[i]);
			curr.index.lazySet(i);
			if (i != a.length - 1) {
				final ListNode nextNode = new ListNode();
				curr.next.lazySet(nextNode);
				curr = nextNode;
			}
		}
	}

	public static void main(String[] args) {
		final ConcurrentList<String> e = new ConcurrentList<String>();
		e.add("Hello");
		e.add("World!");
		e.add("testing");
		JVM.println("index[0]: " + e.get(0));
		JVM.println("index[1]: " + e.get(1));
		JVM.println("index[2]: " + e.get(2));
		JVM.println("nodes: ");
		ArrayUtils.printLln(e.getAllNodes());
		JVM.println("set(2): " + e.set(2, "tested!"));
		JVM.println("Iterator<>: ");
		e.iterator().forEachRemaining((f) -> {
			JVM.println(f);
		});
		JVM.print("toArray: ");
		JVM.println(e.toArray());
		JVM.print("toArray(String[]): ");
		JVM.println(e.toArray(new String[e.size()]));
		JVM.println("remove(2): " + e.remove(2));
		JVM.println("get(2): " + e.get(2));
		e.clear();
		JVM.print("clear: ");
		JVM.println(e.toArray());
		JVM.println("multi-thread-add:");
		ExecutorManager.get().await(ExecutorManager.globalAsyncSubmit(() -> {
			e.add("value 1");
			e.add("value 2");
			return true;
		}), ExecutorManager.globalAsyncSubmit(() -> {
			e.add("value 3");
			e.add("value 4");
			return true;
		}), ExecutorManager.globalAsyncSubmit(() -> {
			e.add("value 5");
			e.add("value 6");
			return true;
		}));
		JVM.println("nodes: ");
		ArrayUtils.printLln(e.getAllNodes());
		JVM.print("current value(s): ");
		JVM.println(e.toArray());
		JVM.println("Iterator<>: ");
		e.iterator().forEachRemaining((f) -> {
			JVM.println(f);
		});
		JVM.println("listIterator(0):");
		final ListIterator<String> s = e.listIterator(0);
		while (s.hasNext()) {
			JVM.println(s.next());
		}
	}

	@Override
	public void forEach(final Consumer<? super E> action) {
		Variables.notNullE(action);
//	     for (E t : this) {
//	    	 action.accept(t);
//	     }
		ListNode curr = this.root.get();
		while (true) {
			if (curr == null)
				break;
			if (!curr.isSet())
				continue;
			if (curr.next() == null) {
				break;
			} else {
				action.accept(curr.value());
				curr = curr.next();
			}
		}
	}

	@SuppressWarnings("unchecked")
	private ListNode[] getAllNodes() {
		if (this.size.get() <= 0)
			return new ConcurrentList.ListNode[0];
		final ListNode[] ln = new ConcurrentList.ListNode[this.size.get()];
		int index = 0;
		ListNode curr = this.root.get();
		while (curr != null && index < ln.length) {
			ln[index] = curr;
			curr = curr.next();
			index += 1;
		}
		return ln;
	}

	@Override
	public Stream<E> stream() {
		return List.super.stream();
	}

	@Override
	public Stream<E> parallelStream() {
		return StreamSupport.stream(spliterator(), true);
	}
}
